package com.example.lcpractice.lc;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * [53]最大子数组和.java
 * //给定一个数组，求这个数组的连续子数组中，最大的那一段的和。
 * <p>
 * 如数组[-2,1,-3,4,-1,2,1,-5,4] 的子段为：
 * <p>
 * [-2,1]、[1,-3,4,-1]、[4,-1,2,1]、...、[-2,1,-3,4,-1,2,1,-5,4]，和最大的是[4,1,2,1]，为6。
 * <p>
 * Input: int [] nums = [-2,1,-3,4,-1,2,1,-5,4],
 * Output: 6
 * Explanation: [4,-1,2,1] has the largest sum = 6.
 */
public class Lc53 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSubArray = maxSubArray(nums);
        System.out.println(maxSubArray);
    }

    /**
     * 1 子问题
     * 只考虑第一个元素，则最大子段和为其本身 DP[0] = nums[0]
     * 考虑前两个元素，最大子段和为 nums[0],num[1]以及 nums[0] + num[1] 中最大值 设为DP[1]
     * 考虑前三个元素，如何求其最大子段和？还是分为两种情况讨论，第三个元素在最后的字串内吗？
     * 若第三个元素也包含在最后的字串内，则DP[2] = Max(DP[1]+nums[2] , nums[2])<br>
     * <p>
     * <p>
     * 2 确认状态
     * DP[i] 为 以nums[i]结尾的子段的最大最短和<br>
     * <p>
     * 例如 DP[1]则为以nums[1]结尾的最大字段和<br>
     * <p>
     * 3 初始状态
     * dp[0] = nums[0]<br>
     * <p>
     * dp[1] = max(dp[0]+nums[1] , nums[1]) <br>
     * <p>
     * 4 状态转移方程：
     * dp[i] = max(dp[i-1]+nums[i],nums[i])
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < len; i++) {
            //之前的子串最大值加目前数字
            int curAddSubArr = dp[i - 1] + nums[i]; // dp[i]代表以i结尾的最大的字串和
            // **最重要**当前连上前字串的和，以及单独当前值 ，取最大（如果联立最大则象征连链，否则断链，重新计数链）
            dp[i] = Math.max(curAddSubArr, nums[i]);
            //每一次取值都比较最大，方便返回
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }


}
